package com.cet.qz.unit01.chapter1_1;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdRandom;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description:随机匹配
 * @author: 陈恩涛
 * @create: 2021-01-10 21:48
 **/
public class Exec05 {

    public static int binarySearch(int[] a, int key, int lo, int hi) {
        if(lo > hi)
            return -1;
        int mid = lo + (hi - lo)/2;
        if(a[mid] == key)
            return mid;
        else if(a[mid] > key)
            return binarySearch(a,key,lo,mid -1);
        else
            return binarySearch(a,key,mid+1,hi);
    }

    /*
     *方法描述：二分查找
     *
     * @param a
     * @param key
     * @return int
     * @author chenentao
     * @date 2021/1/10 21:59
     */
    public static int binarySearch(int[] a,int key) {
        return binarySearch(a,key,0,a.length-1);
    }

    /*
     *方法描述： 生成一个长度为N的6位随机正整数的数组
     *
     * @param N
     * @return int[]
     * @author chenentao
     * @date 2021/1/10 22:05
     */
    public static int[] genRandomArray(int N) {
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
             a[i]= StdRandom.uniform(100000, 1000000);
        }
        return a;
    }

    /*
     *方法描述： 找出同时存在于两个数组中的整数数量
     *
     * @param a
     * @param b
     * @return int
     * @author chenentao
     * @date 2021/1/10 22:12
     */
    public static int getNumOfSameElement(int[] a,int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            if(binarySearch(b,a[i]) != -1)
                count++;
        }
        return count;
    }

    public static void test(int T){
        int[] n = {1000,10000,100000,1000000};
        for (int N : n) {
            int count = 0;
            for (int i = 0; i < T; i++) {
                int[] a = genRandomArray(N);
                int[] b = genRandomArray(N);
                count += getNumOfSameElement(a, b);
            }
            double average = count*1.0/T;
            System.out.println(N+"-->"+average);
        }
    }

    public static void main(String[] args) {
        //从命令行接收实验运行遍数T
        System.out.println("请输入实验次数：");
        int T = StdIn.readInt();
        test(T);
    }
}
